package com.sunkq.algorithms;

import org.junit.Test;

import java.util.LinkedList;
import java.util.List;

public class MergeTest2 {


    @Test
    public void testCountSmaller(){
        int[] nums = new int[]{5,2,6,1};
        List<Integer> res = countSmaller(nums);
        System.out.println(res);
    }

    public List<Integer> countSmaller(int[] nums) {
        int n = nums.length;
        temp = new Pair[n];
        count = new int[n];
        Pair [] arr = new Pair[n];
        for (int i = 0; i < nums.length; i++) {
            arr[i] = new Pair(nums[i],i);
        }
        sort(arr,0,n-1);
        List<Integer> res = new LinkedList<>();
        for (int c : count) res.add(c);
        return res;
    }

    private class Pair{
        private int val;
        private int id;
        Pair(int val,int id){
            this.val = val;
            this.id = id;
        }
    }

    private Pair[] temp;
    private int[] count;



    private void sort(Pair[] arr,int lo,int hi){
        if (lo == hi) return;
        int mid = lo + (hi-lo)/2;
        sort(arr,lo,mid);
        sort(arr,mid+1,hi);
        merge(arr,lo,mid,hi);
    }

    private void merge(Pair[] arr,int lo,int mid,int hi){
        for (int i = lo; i <= hi; i++) {
            temp[i] = arr[i];
        }

        int i = lo, j = mid + 1;
        for (int p = lo; p <= hi; p++) {
            if (i == mid + 1) {
                arr[p] = temp[j++];
            } else if (j == hi + 1) {
                arr[p] = temp[i++];
                // 更新 count 数组
                count[arr[p].id] += j - mid - 1;
            } else if (temp[i].val > temp[j].val) {
                arr[p] = temp[j++];
            } else {
                arr[p] = temp[i++];
                // 更新 count 数组
                count[arr[p].id] += j - mid - 1;
            }
        }
    }
}
